package leetcode_1000;

import java.util.LinkedList;
import java.util.Queue;

/**
 *@author 周杨
 *ShortestBridge_934 有两个小岛在二维矩阵中 问最少翻转多少个0使两个岛变成一个岛
 *describe:DFS+BFS BFS需要有策略 AC 75%
 *2018年11月21日 上午10:12:09
 */
public class ShortestBridge_934_ {
	public static void main(String[] args) {
		ShortestBridge_934_ test=new ShortestBridge_934_();
		int A[][]=new int[][] {{0,0,0,1,1},{0,0,0,1,0},{0,0,0,1,1},{0,0,1,0,1},{0,0,1,1,0}};
		test.shortestBridge(A);
	}

	public int shortestBridge(int[][] A) {
	        boolean found = false ;
	        int createBridge = 0 ;
	        Queue<int[]> queue = new LinkedList<>() ;
	        int [][] directions = new int[][]{{0,1},{1,0},{0,-1},{-1,0}} ;
	        //dfs区分开两个小岛
	        for(int i=0;i<A.length;i++){
	            for(int j=0;j<A[0].length;j++){
	                if(!found&&A[i][j]==1){
	                    dfs(A, i, j) ;
	                    found = true ;
	                }
	                if(found&&A[i][j]==1){
	                    queue.offer(new int[]{i,j}) ;
	                }
	            }
	        }
	        //bfs建桥直两个岛屿相连接
	        while(!queue.isEmpty()){
	            int size = queue.size() ;
	            for(int i=0;i<size;i++){
	                int point[] = queue.poll() ;
	                for(int[] direction :directions){
	                    int x = point[0] + direction[0] ;
	                    int y = point[1] + direction[1] ;
	                    if(x<0||x>=A.length||y<0||y>=A[0].length||A[x][y]==1){
	                        continue;
	                    }else if(A[x][y] == 2){
	                        return createBridge ;
	                    }else{
	                        A[x][y] = 1 ;
	                        queue.offer(new int[]{x,y}) ;
	                    }
	                }
	            }
	            createBridge ++ ;
	        }
	        return 1 ;
	    }

	    public void dfs(int A[][], int x, int y){
	        if(x<0||x>= A.length||y<0||y>=A[0].length||A[x][y]==2||A[x][y]==0){
	            return;
	        }
	        A[x][y] = 2 ;
	        dfs(A, x+1, y) ;
	        dfs(A, x-1, y) ;
	        dfs(A, x, y+1) ;
	        dfs(A, x, y-1) ;
	    }
	
	
	/**
	 * describe:深搜和广搜结合 超时 因为我是根据0开始广搜  那么42/96超时 如果根据1开始广搜 搜到2 那么47/96超时
	 * 2018年11月21日 上午9:57:57
	 */
	public int shortestBridge1(int[][] A) {
        out:for(int i=0;i<A.length;++i)
        	for(int j=0;j<A[0].length;++j) {
        		if(A[i][j]==1) {
        			dfs(A,i,j);
        			break out;//给不同的岛上不同的色
        		}
        	}
		int min=Integer.MAX_VALUE;
		for(int i=0;i<A.length;++i)
			for(int j=0;j<A[0].length;++j) {
				if(A[i][j]==1) {
					min=Math.min(min, bfs(A,i,j,2));
				}
			}
		return min;	
    }
	
	public void dfs1(int [][]A,int x,int y) {
		if(x>=0&&x<A.length&&y>=0&&y<A[0].length&&A[x][y]==1) {
			A[x][y]=2;
			dfs1(A,x+1,y);
			dfs1(A,x-1,y);
			dfs1(A,x,y+1);
			dfs1(A,x,y-1);
		}
	}
	
	public int bfs(int [][]A,int x,int y,int term) {
		Queue<int[]> queue=new LinkedList<int[]>();
		boolean dp[][]=new boolean[A.length][A[0].length];
		queue.add(new int[] {x,y});
		int res=0;
		while(!queue.isEmpty()) {
			int size=queue.size();
			while(size--!=0) {
				int[] now=queue.poll();
				x=now[0];
				y=now[1];
				dp[x][y]=true;
				if(x-1>=0) {
					if(A[x-1][y]==term)
						return res;
					if(A[x-1][y]==0)
						if(!dp[x-1][y])
							queue.add(new int[] {x-1,y});
				}
				if(y-1>=0) {
					if(A[x][y-1]==term)
						return res;
					if(A[x][y-1]==0)
						if(!dp[x][y-1])
							queue.add(new int[] {x,y-1});
				}
				if(x+1<A.length) {
					if(A[x+1][y]==term)
						return res;
					if(A[x+1][y]==0)
						if(!dp[x+1][y])
							queue.add(new int[] {x+1,y});
				}
				if(y+1<A[0].length) {
					if(A[x][y+1]==term)
						return res;
					if(A[x][y+1]==0)
						if(!dp[x][y+1])
							queue.add(new int[] {x,y+1});
				}
			}
			++res;
		}
		return 10000;//走不到
	}
}
